package com.study.algorithm.niuke.practice;

/**
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，
 * 向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，
 * 则该路径不能再进入该格子。 例如   矩阵中包含一条字符串"bcced"的路径，
 * 但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后
 * ，路径不能再次进入该格子。
 * <p>
 * 我是使用深度遍历做的
 */
public class HavePath {

    private final int top = 0;
    private final int right = 1;
    private final int foot = 2;
    private final int left = 3;

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix.length == 0) {
            return false;
        }
        int maxVisitedIndex = rows * cols;

        int[] visited = new int[maxVisitedIndex + 1];
        for (int currRow = 0; currRow < rows; currRow++) {
            for (int currCol = 0; currCol < cols; currCol++) {
                if (isPath(visited, matrix, currRow, currCol, 0, rows, cols, str)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isPath(int[] visited, char[] matrix, int currRow, int currCol, int index, int rows, int cols, char[] str) {
        if (index == str.length) {
            return true;
        }
        if (isOutOfEdge(currRow, currCol, rows, cols)) {
            return false;
        }

        int visitedIndex = currRow * cols + currCol;
        if (visited[visitedIndex] == 1) {
            return false;
        }
        if (isMatchCurrDestStr(matrix, visitedIndex, index, str)) {
            visited[visitedIndex] = 1;
            int nextMatchIndex = index + 1;
            //top
            if (isPathForNextDirection(top, visited, matrix, currRow, currCol, nextMatchIndex, rows, cols, str)) {
                return true;
            }
            if (isPathForNextDirection(right, visited, matrix, currRow, currCol, nextMatchIndex, rows, cols, str)) {
                return true;
            }
            if (isPathForNextDirection(foot, visited, matrix, currRow, currCol, nextMatchIndex, rows, cols, str)) {
                return true;
            }
            if (isPathForNextDirection(left, visited, matrix, currRow, currCol, nextMatchIndex, rows, cols, str)) {
                return true;
            }
            visited[visitedIndex] = 0;
        }
        return false;

    }

    private boolean isPathForNextDirection(int direction, int[] visited, char[] matrix, int row, int col, int index, int rows, int cols, char[] str) {
        int currRow = row;
        int currCol = col;
        if (top == direction) {
            currRow--;

        }
        if (right == direction) {
            currCol++;
        }
        if (foot == direction) {
            currRow++;
        }
        if (left == direction) {
            currCol--;
        }

        return isPath(visited, matrix, currRow, currCol, index, rows, cols, str);
    }


    private boolean isOutOfEdge(int currRow, int currCol, int rows, int cols) {
        return !(currRow >= 0 && currRow < rows && currCol >= 0 && currCol < cols);
    }


    private boolean isMatchCurrDestStr(char[] matrix, int visitedIndex, int index, char[] str) {
        char currStr = matrix[visitedIndex];
        char destStr = str[index];

        return currStr == destStr;
    }

}
